package com.mlh.dp.old;
/*
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

举例:
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
* */

public class DeleteToPoint {
    //这题没有思考出来，basecase很好想出来，当时怎么递归下去想不到
    //实际上这题和打家劫舍很像，但当时只是意识到，但是不知道怎么转化
    //当时是想到要不要先排序，这样好处理一点，但是这样如果数组中有相同的值就不好处理了
    //这题的难点实际上是在对数组的处理

    //这边对数组的处理是看题解的
    //他是构建一个数组，新数组的索引代表原本数组中的元素，新数组的元素代表索引在原数组中出现的次数
    //经过这么一构建，直接将问题转化成打家劫舍问题

    public static void main(String[] args) {
        int[] nums = {1,2,3,15,16,17,18};
        System.out.println(method2(processArr(nums)));
    }

    //暴力递归（假设传进来的是已经处理好的数组）
    public static int method1(int[]nums,int index){
       if(index>=nums.length){
           return 0;
       }
       return Math.max(method1(nums,index+2)+index*nums[index], method1(nums,index+1));

    }

    public static int method2(int[]nums){
        int[] score=new int[nums.length];
        score[0]=0;
        score[1]=nums[1];
        for(int i=2;i<score.length;i++){
            score[i]=Math.max(score[i-2]+i*nums[i],score[i-1]);
        }
        for(int temp:score){
            System.out.print(temp+" ");
        }
        return score[score.length-1];
    }

    //第一遍写得 写得太丑陋了
    public static int[] processArr(int[]nums){
        int[]processed=new int[2*10000+1];
        System.out.println(processed.length);
        int counter;
        for(int i=0;i<processed.length;i++){
            counter=0;
            for(int j=0;j<nums.length;j++){
                if(i==nums[j]){
                    counter++;
                }
            }
            processed[i]=counter;
        }
        return processed;
    }

    public static int[] processArr2(int[]nums){
        int maxValue=-1;
        for(int temp:nums){
            if(temp>maxValue){
                maxValue=temp;
            }
        }
        int[] processed=new int[maxValue+1];
        for(int temp:nums){
           processed[temp]++;
        }
        return processed;
    }

}
